# 最大异或节点
# 可以参考leetcode的421题: https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/
# 关于异或的题目还有260题: https://leetcode.cn/problems/single-number-iii/description/
# 异或运算:
#   1 ^ 1 = 0
#   0 ^ 0 = 0
#   1 ^ 0 = 1
#   0 ^ 1 = 1
# 特性:
#   X ^ 0 = X
#   X ^ X = 0
from collections import defaultdict


def get_max_num(arr1, arr2):
    """我测试时候的答案, 暴力解法: 每个节点逐个对比并取异或的最大值, 若两个节点相邻则跳过
    监测点: 通过/超时 = 10/10"""
    n = len(arr1)
    res = 0
    for i in range(n):
        for j in range(i, n):
            if (j == -1 and arr2[j] == i) or (i == -1 and arr2[i] == j):  # 判断是否为相邻的两个节点
                continue
            res = max(arr1[i] ^ arr1[j], res)
    return res


def get_max_xor(nums, parent) -> int:
    """
    参考lc421
    """
    n = len(nums)
    graph = [set() for _ in range(n)]
    for son, pa in enumerate(parent):
        if pa == -1:
            continue
        graph[pa].add(son)
        graph[son].add(pa)

    ans = mask = 0
    high_bit = max(nums).bit_length() - 1  # 最高位
    for i in range(high_bit, -1, -1):  # 从最高位开始枚举
        mask |= 1 << i
        new_ans = ans | (1 << i)  # 尝试将当前位设为1作为候选答案
        seen = defaultdict(list)
        is_valid = False  # 两个节点是否为非直接连接的
        for j, x in enumerate(nums):  # 遍历集合中的所有数字
            if is_valid:
                break
            x &= mask  # 仅保留掩码对应的位
            if new_ans ^ x in seen:  # 检查当前是否有异或为1的, 即该位是否可以为1, 若 A ^ B = new_ans 那么 A = B ^ new_ans
                for node in seen[x ^ new_ans]:  # 检查是否是直接连接的节点
                    if node not in graph[j]:
                        ans = new_ans  # 如果存在，则当前位可以保留为1
                        is_valid = True
                        break

            if x in seen:
                seen[x].append(j)
            else:
                seen[x] = [i]
    return ans


print(get_max_num([1, 0, 5, 3, 4], [-1, 0, 1, 0, 1]))
print(get_max_xor([1, 0, 5, 3, 4], [-1, 0, 1, 0, 1]))
